P3704 [SDOI2017]数字表格

前置知识:莫比乌斯反演,数论分块

题意

i=1nj=1mfgcd(i,j)\prod_{i=1}^n \prod_{j=1}^m f_{ gcd(i,j) }

其中ff为斐波拉契数列

Part 1.正常操作

gcdgcd可以枚举,令d=min(n,m)d=min(n,m),上式等价于

k=1di=1nj=1mfk[gcd(i,j)==k]\prod_{k=1}^d\prod_{i=1}^n\prod_{j=1}^mf_k^{[ gcd(i,j)==k ]}

将重复的fkf_k计算到一起

k=1dfki=1nj=1m[gcd(i,j)==k]\prod_{k=1}^df_k^{\sum_{i=1}^n\sum_{j=1}^m[ gcd(i,j)==k ]}

k=1dfki=1n/kj=1m/k[gcd(i,j)==1]\prod_{k=1}^df_k^{\sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }[ gcd(i,j)==1 ]}

Part2.毒瘤操作

将指数部分拿出来看:

i=1n/kj=1m/k[gcd(i,j)==1]\sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }[ gcd(i,j)==1 ]

有一个结论:

inμ(i)=[n=1]\sum_{i \mid n}\mu(i)=[n=1]

证明如下:

1.当n=1n=1时显然

2.当n!=1n!=1时,由唯一分解定理得:n=p1w1p2w2...pkwkn=p_1^{w_1}p_2^{w_2}...p_k^{w_k}
由莫比乌斯函数的性质,μ(k)=0\mu(k) \not= 0当且仅当kk无平方因子。(由多个质因子相乘)

ii个质因子的数有CkiC_k^i种取值。

所以只需证

i=0k(1)iCki=0\sum_{i=0}^k(-1)^iC_k^i=0

很像二项式定理,将 x=1,y=1x = 1 , y = -1 代入即可得证。

代入上式

i=1n/kj=1m/ksgcd(i,j)μ(s)\sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }\sum_{s \mid gcd(i,j)}\mu(s)

改写一下:

i=1n/kj=1m/ks=1n/kμ(s)[sgcd(i,j)]\sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }\sum_{s=1}^{ \lfloor n/k \rfloor }\mu(s)* [s \mid gcd(i,j)]

μ(s)\mu(s)向前提:

s=1n/kμ(s)i=1n/kj=1m/k[sgcd(i,j)]\sum_{s=1}^{ \lfloor n/k \rfloor } \mu(s) \sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }[s \mid gcd(i,j)]

s=1n/kμ(s)nksmks\sum_{s=1}^{ \lfloor n/k \rfloor } \mu(s)\lfloor \frac{n}{ks} \rfloor \lfloor \frac{m}{ks} \rfloor

然后,我们得到最终结果为:

k=1dfks=1n/kμ(s)nksmks\prod_{k=1}^df_k^{\sum_{s=1}^{ \lfloor n/k \rfloor } \mu(s)\lfloor \frac{n}{ks} \rfloor \lfloor \frac{m}{ks} \rfloor}

T=ksT=ks,则原式等价于:

T=1dkTfkμ(Tk)nTmT\prod_{T=1}^d\prod_{k \mid T }f_k^{\mu(\frac{T}{k})\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor}

nT,mT\lfloor \frac{n}{T} \rfloor , \lfloor \frac{m}{T} \rfloor与枚举的kk无关,可以加括号

T=1d(kTfkμ(Tk))nTmT\prod_{T=1}^d(\prod_{k \mid T }f_k^{\mu(\frac{T}{k})})^{\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor}

然后令F(T)=kTfkμ(Tk)F(T)=\prod_{k \mid T }f_k^{\mu(\frac{T}{k})},原式化为

T=1dF(T)nTmT\prod_{T=1}^dF(T)^{\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor}

似乎就不能化简了

Part3.求解

内部的F(k)F(k)可以用类似埃筛的思想解决,外部用数论分块,就可以Θ(n)\Theta(\sqrt{n})解决了

#include <cstdio>
#include <iostream>
using namespace std;
#define Mod 1000000007

const int MAXN = 1000000;
int k , prime[ MAXN / 10 + 5 ] , mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

void sieve( int x ) {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= x ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ k ] = i;
			mu[ i ] = -1;
		}
		for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= x ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
			mu[ i * prime[ j ] ] = -mu[ i ];
		}
	}
}
int Quick_pow( int x , int po ) {
	int Ans = 1;
	while( po ) {
		if( po % 2 ) 
			Ans = 1ll * Ans * x % Mod;
		x = 1ll * x * x % Mod;
		po /= 2;
	}
	return Ans;
}
int Inv( int x ) {
	return Quick_pow( x , Mod - 2 );
} 

int t , n , m;
int f[ MAXN + 5 ] = { 0 , 1 , 1 } , finv[ MAXN + 5 ] = { 0 , 1 , 1 } , F[ MAXN + 5 ];
void Init( ) {
	sieve( MAXN );
	for( int i = 3 ; i <= MAXN ; i ++ ) {
		f[ i ] = ( f[ i - 1 ] + f[ i - 2 ] ) % Mod;
		finv[ i ] = Inv( f[ i ] ); 
	}
	for( int i = 0 ; i <= MAXN ; i ++ )
		F[ i ] = 1;
	for( int i = 1 ; i <= MAXN ; i ++ ) {
		if( !mu[ i ] ) continue;
		for( int j = i ; j <= MAXN ; j += i )
			F[ j ] = ( 1ll * F[ j ] * ( mu[ i ] == 1 ? f[ j / i ] : finv[ j / i ] ) ) % Mod;
	}
	for( int i = 2 ; i <= MAXN ; i ++ )
		F[ i ] = 1ll * F[ i - 1 ] * F[ i ] % Mod;
}

int solve( int n , int m ) {
	int d = n < m ? n : m , Ans = 1;
	for( int l = 1 , r ; l <= d ; l = r + 1 ) {
		r = min( n / ( n / l ) , m / ( m / l ) );
		Ans = 1ll * Ans * Quick_pow( 1ll * F[ r ] * Inv( F[ l - 1 ] ) % Mod , 1ll * ( n / l ) * ( m / l ) % ( Mod - 1 ) ) % Mod;
	}
	return ( Ans + Mod ) % Mod;
}

int main( ) {
	Init( );	
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d %d",&n,&m);
		printf("%d\n",solve( n , m ));
	}
	return 0;
}